Transmitting data between a source node and destination node along multiple paths of a network is well-recognised, at least in principle, as an effective technique to improve performance (reduce delay, increase throughput etc.) and resilience (if one path breaks, the connection can gracefully failover to the remaining paths).
Such source and destination nodes would typically comprise a number of network interfaces, each using different technologies to access the Internet such as cellular networks or fixed access networks as well as wired or wireless local access networks. These technologies exhibit different quality characteristics in terms of coverage, capacity, power consumption, geographical availability and cost.
Building an efficient, practically usable multi-path transfer mechanism remains highly challenging. One major issue is packet re-ordering. Referring to FIG. 1, when a source (sender) node stripes packets across multiple paths such as a slow path and a fast path as shown in FIG. 1, differences in transmission delay of the paths means that packets can arrive in a different order from which they were sent.
Thus, in the example, an application running on a destination node has received packets 1 and 2. However, in common with many applications, the application in FIG. 1 requires in-order packet delivery at the destination (receiver). Thus, the application cannot process any of received packets 4-6 until packet 3 has been received.
Note that transmission delay along a path can easily vary rapidly by a factor of 2 or more due to queueing and congestion. So where packet 3, either knowingly or unexpectedly, has been transmitted through the slow path, i.e. where it has incurred a transmission delay, this in turn imposes a re-ordering delay on the processing of packets 4-6 while they are held in a re-ordering buffer.
Re-ordering can translate into increased delay, perhaps greatly increased delay for an application. This issue is greatly exacerbated by any unpredictable, time-varying nature of the transmission delay as well as packet loss rate on each path.
Clearly, if the transmission delay of each path were fixed and known i.e. deterministic, it would be possible to schedule the transmission of packets across each of the paths between a source and destination node so that packets would arrive in-order and so no re-ordering delay would be incurred. However, where transmission delay is not certain, because of the stochastic nature of the underlying network paths, then a problem arises in scheduling packets for transmission across different paths with a minimum of re-ordering delay.
FIG. 2 illustrates why failure to consider the randomness of the delays inherent to real-life communication paths when scheduling transmission of packets may lead to re-ordering delays. In this example, two packets 1, 2 have to be scheduled across two paths/links or interfaces with identical average one-way delay. A deterministic scheduler that only considers the expectation of the paths' delays may schedule packet 1 in a high variance or volatile path, forcing packet 2 to await in the receiver's buffer for packet 1 during slower transmission times for packet 1, thus growing the expected re-ordering delay.
At larger scales, when many paths and/or packets are to be scheduled, a deterministic scheduler could lead to high re-ordering delays, particularly when some paths have large variances.
Previous work on multi-path packet transmission has considered joint congestion control across the paths including: joint control of the rate at which packets are sent for example, as disclosed in EP2537301 and U.S. Pat. No. 8,780,693; use of multiple paths for load balancing, as disclosed in U.S. Pat. No. 8,036,226; mobility when using multiple paths and multi-path connection establishment as disclosed in U.S. Pat. No. 8,824,480; selection of which interface from the available interfaces on which to route a flow as disclosed in U.S. Pat. No. 7,230,921; and selection of the path along which to send feedback reports from the receiver as disclosed in US2013/0077501.
However, these have not addressed the problem outlined above in handling the scheduling of packets which are to be transmitted over multiple network paths exhibiting non-deterministic transmission delays.